package com.leetcode.no34;

import java.util.LinkedList;
import java.util.List;

public class Solution {
    public int[] searchRange(int[] nums, int target) {

        int find = binarySearch(nums, target);
        //如果没找到，返回{-1, -1}
        if (find == -1)
            return new int[]{-1, -1};

        int left = find - 1;
        int right = find + 1;

        while (left >= 0 && nums[left] == target) {
            left--;
        }

        while (right <= nums.length && nums[right] == target) {
            right++;
        }

        return new int[]{left + 1, right - 1};
    }

    private int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midVal = nums[mid];

            if (midVal == target) {
                return mid;
            } else if (midVal < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}
